package danran.bfs;

import java.util.*;

/**
 * @Classname CourseSche
 * @Description TODO
 * @Date 2021/8/27 15:46
 * @Created by ASUS
 */
public class CourseSche {

    public static void main(String[] args) {


        System.out.println(new CourseSche().can(5, new int[][]{{1, 0}, {2, 1}, {3, 4}, {4, 3}}));
    }

    public boolean can(int numCourses, int[][] prerequisites) {
        if (prerequisites.length <= 1) return true;
        Map<Integer, List<Integer>> g = new HashMap<>();
        int[] in = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int start = prerequisites[i][1], end = prerequisites[i][0];
            in[end]++;

            List<Integer> children;
            if (!g.containsKey(start)) {
                children = new ArrayList<>();
            } else {
                children = g.get(start);
            }
            children.add(end);
            g.put(start, children);
            if (!g.containsKey(end)) g.put(end, new ArrayList<>());
        }
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0 && !dfs(g, i, new HashSet<>())) return false;
        }

        return true;
    }

    public boolean dfs(Map<Integer, List<Integer>> g, int start, Set<Integer> visited) {
        List<Integer> children = g.getOrDefault(start, new ArrayList<>());
        if (children.size() == 0) return true;
        visited.add(start);
        for (Integer child : children) {
            if (visited.contains(child)) return false;
            visited.add(child);
            if (!dfs(g, child, visited)) return false;
            visited.remove(child);
        }
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites.length <= 1) return true;
        Map<Integer, List<Integer>> g = new HashMap<>();
        int[] in = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int start = prerequisites[i][1], end = prerequisites[i][0];
            in[end]++;

            List<Integer> children;
            if (!g.containsKey(start)) {
                children = new ArrayList<>();
            } else {
                children = g.get(start);
            }
            children.add(end);
            g.put(start, children);
            if (!g.containsKey(end)) g.put(end, new ArrayList<>());
        }
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < in.length; i++) {
            if (in[i] == 0) q.offer(i);
        }
        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Integer cur = q.poll();
                cnt++;
                List<Integer> children = g.getOrDefault(cur, new ArrayList<>());
                for (Integer child : children) {
                    in[child]--;
                    if (in[child] == 0) q.offer(child);
                }
            }
        }
        return cnt == numCourses;
    }
}
